/*
 * Copyright (c) 2010 Mathew Hall, University of Sheffield.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following conditions
 * are met:
 *
 * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following
 * disclaimer in the documentation and/or other materials provided
 * with the distribution.
 *
 * Neither the name of the University of Sheffield nor the names of its
 * contributors may be used to endorse or promote products derived
 * from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */
package primitives.cluster;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Set;
import java.util.HashSet;
import java.util.Stack;
import primitives.graph.Graph;
import primitives.graph.Node;
import primitives.util.UndefinedIndexException;

public abstract class ClusterUtils {

    //move child from a to b
    //if a becomes empty then delete a and add all its old ids to b
	/***
	 * To becomes the new parent of node. This method migrates node to a new parent.
	 * 
	 * @param node the node to move
	 * @param from the current parent of node
	 * @param to the new parent of mode
	 * @param tree the tree this operation takes part in. Will be modified.
	 * @param prune should empty clusters created as a result be removed?
	 * @return the modified tree. Does in-place so this is equal to tree parameter.
	 */
    public static ClusterHead move(IClusterLevel node, ClusterNode from, ClusterNode to, ClusterHead tree, boolean prune) {


        if (to != null && to.encapsulates() && from != null && node != null) {
            from.deleteChild(node);
            to.addChild(node);
            //if from has no clusterleaves, just copy all of its ids over to to.
            if (prune && from.getSize() == 0) {
                for (int i : from.getIDs()) {
                    to.setID(i);
                }
                deleteClusterLevelFromTree(from,tree);
            }

        }else{
            System.err.println("ERROR");
        }
        return tree;
    }

	/**
	 * To becomes the new parent of node, empty nodes are removed. This is the equivalent
	 * of calling move with prune set to true.
	 * @see #move(primitives.cluster.IClusterLevel, primitives.cluster.ClusterNode, primitives.cluster.ClusterNode, primitives.cluster.ClusterHead, boolean prune) 
	 * @param node
	 * @param from
	 * @param to
	 * @param tree
	 * @return 
	 */
    public static ClusterHead move(IClusterLevel node, ClusterNode from, ClusterNode to, ClusterHead tree) {
        return move( node,  from,  to,  tree, true);
    
    }

	@Deprecated
    public static ClusterHead explode(ClusterNode toSplit, ClusterNode parent, ClusterHead tree) {
        Queue<ClusterNode> added = new LinkedList<ClusterNode>();
        for (int id : toSplit.getIDs()) {
            ClusterNode newC = new ClusterNode();
            newC.setID(id);
            parent.addChild(newC);
            added.add(newC);
        }

        for (IClusterLevel c : toSplit.getChildren()) {
            ClusterNode n = added.remove();
            n.addChild(c);
            added.add(n);

        }
        return ClusterUtils.deleteClusterLevelFromTree(toSplit, tree);

    }

    /**
	 * Add an empty ClusterNode below parent. This method creates a new ClusterNode
	 * and adds it to parent's children. It will search all IDs in the whole tree
	 * for the lowest unused ID.
	 * @return a new ClusterNode with an ID set to the lowest unused one.
	 */
    public static ClusterNode addEmpty(ClusterNode parent, ClusterHead tree) {
        int i = 0;
        HashSet<Integer> ids = new HashSet<Integer>(); ids.addAll(getIDs(tree));

        do {
            if (!ids.contains(i)) {
                assert (parent.encapsulates());
                ClusterNode c = new ClusterNode();
                c.setID(i);
                parent.addChild(c);
                return tree;
            }
            i++;
        } while (true);
    }

	/**
	 * Add a new ClusterNode below parent, without setting its ID. This method
	 * adds a new ClusterNode below parent but does so without assigning the lowest
	 * valid ID, instead setting it to -2.
	 * @return the new node added, with ID -2.
	 */
    public static ClusterNode addEmptyIgnoreID(ClusterNode parent, ClusterHead tree) {


            assert (parent.encapsulates());
            ClusterNode c = new ClusterNode();
            c.setID(-2);
            parent.addChild(c);
            return c;
        
    }

    /**
	 * Remove a cluster from the tree. This removes toBeRemoved from the tree by finding
	 * its parent and calling deleteChild on it. The argument will not be modified, nor
	 * will any kind of migration occur for nodes within toBeRemoved. Don't use this method
	 * without dealing with the children. If toBeRemoved will be made the child of another node,
	 * {@link #move(primitives.cluster.IClusterLevel, primitives.cluster.ClusterNode, primitives.cluster.ClusterNode, primitives.cluster.ClusterHead)} should be used instead.
	 * @param toBeRemoved
	 * @param tree
	 * @return 
	 */
	@Deprecated
    public static ClusterHead deleteClusterLevelFromTree(IClusterLevel toBeRemoved, ClusterHead tree) {
        IClusterLevel parent = findParent(toBeRemoved, tree);
        if (parent != null && parent.encapsulates()) {
            ((ClusterNode) parent).deleteChild(toBeRemoved);
        }
        return tree;
    }

	/***
	 * Locates the parent of a node.
	 * @param searchterm a cluster whose parent is sought
	 * @param tree the tree in which the search takes place.
	 * @return the parent of searchterm or null if the parent could not be found or if tree == searchterm
	 */
    public static ClusterNode findParent(IClusterLevel searchterm, IClusterLevel tree) {
        if (tree == searchterm) {
            return null;
        }
        if (tree.encapsulates()) {
            ClusterNode cast = (ClusterNode)tree;
            if (cast.getChildren().contains(searchterm)) {
                return cast;
            }
            for (IClusterLevel t : cast.getChildren()) {
                ClusterNode res = findParent(searchterm, t);
                if (res != null) {
                    return res;
                }
            }
        }
        return null;
    }

	/**
	 * Determines if a tree contains all nodes from a graph.
	 * @param tree the tree representation that should have all nodes from representation
	 * @param representation nodes to be searched for in tree
	 * @return true if all nodes from tree are present in representation and vice versa.
	 */
    public static boolean validTree(ClusterHead tree, Graph representation) {
        ///TODO: need to check for intercluster duplication as well as set size.
        return (tree.getNodes().containsAll(representation.getNodes())
                && representation.getNodes().containsAll(tree.getNodes()));
        //return false if:
        // the tree has less nodes than the graph
        // there are duplicated nodes between the child clusters
        //otherwise return true.
    }

    /**
     * Searches the tree for a subcluster with a given ID number.
     * Subclusters are assigned a unique identifier which is used by
     * programs the interpreter runs.  The parameter should always
     * be at most the size of the graph; identifiers start at 0
     * and go to the initial size of the clustering which is always
     * equal to the size of the set of nodes in the graph.
     * This may require some adaptation in future.
     * TODO: write code to snap a given non-found integer to a found one
     * TODO: or just make clusters store IDs of their old merged ones.
     * @param tree the tree to perform the lookupIndexInTree in
     * @param index the ID number to search for
     * @return the cluster node with that ID
     * @throws UndefinedIndexException if the ID isn't found, which can be
     * 	used to default to some valid node, the selection of it isn't defined.
     */
    public static IClusterLevel lookupIndexInTree(int index, ClusterNode tree) throws UndefinedIndexException {
        //TODO: make sure we don't accidentally assign tree to the result of this fn
        
        Queue<IClusterLevel> toVisit = new LinkedList<IClusterLevel>();
        toVisit.offer(tree);

        while(!toVisit.isEmpty()){

            IClusterLevel current = toVisit.remove();

            if (current.knownAs(index)) {
                return current;
            }

            Set<IClusterLevel> kids = ((ClusterNode)current).getChildren();

            for (IClusterLevel c : kids) {
                if (c.knownAs(index)) {
                    return c;
                }
            }
            for (IClusterLevel c : kids) {
                if (c.encapsulates() && c != tree) {
                    toVisit.offer(c);
                }
            }
        }
        throw new UndefinedIndexException("ClusterUtils.lookup - ID number " + index + " not found in tree.", tree);
    }


	/**
	 * Locates the ClusterNode containing n. This method will return the ClusterNode
	 * in the tree which has n as its child.
	 * @param n
	 * @param tree
	 * @return a ClusterNode containing n.
	 * @throws UndefinedIndexException if n cannot be found in the tree.
	 */
    public static IClusterLevel lookup(Node n, ClusterNode tree) throws UndefinedIndexException {
        //TODO: make sure we don't accidentally assign tree to the result of this fn
        boolean isParentOfLeaf = true;

        Set<IClusterLevel> kids = tree.getChildren();
        for (IClusterLevel c :kids){
            if(c.encapsulates()) isParentOfLeaf = false;
        }


        if (tree.getNodes().contains(n) && isParentOfLeaf) {
          return tree;
        }

        for (IClusterLevel c :kids) {
            if (c.getNodes().contains(n)) {
                try{return lookup(n, (ClusterNode)c);}catch(Exception e){}
            }
        }
        
        throw new UndefinedIndexException("ClusterUtils.lookup - ID number " + n + " not found in tree.", tree);
    }

    /**
     * Merges two cluster nodes to one node.
     * Nodes from toberemoved will be placed in parent and toberemoved deleted from the tree.
     * TODO: feed the old ID for toberemoved to parent.
     * @param tree the tree in which to perform the operation
     * @param parent the node which will adopt the children of toberemoved
     * @param toberemoved the node to be removed from the tree.
     * @return
     */
    public static IClusterLevel merge(IClusterLevel toberemoved, IClusterLevel parent, ClusterNode tree) {
        if (parent == toberemoved) {
            return tree;
        }
        //if(parent.getID() == toberemoved.getID()) return tree;

        //if(!toberemoved.encapsulates()) return tree;
        //if(!parent.encapsulates()) return tree;
        if (parent.equals(toberemoved)) {
            return tree;
        }

        //if both encapsulate do whatever
        //if one encapsulates make it inherit the other's Nodes
        //if neither encapsulate add nodes to other


        if (parent.encapsulates() && toberemoved.encapsulates()) {
            Set<IClusterLevel> children = ((ClusterNode) toberemoved).getChildren();
            tree.deleteChild(toberemoved); //?
            //((ClusterNode) parent).deleteChild(toberemoved); //?
            for (Integer i : toberemoved.getIDs()) {
                parent.setID(i);
            }
            for (IClusterLevel c : children) {
                if (c != parent) {
                    ((ClusterNode) parent).addChild(c);
                }
            }
        } else if (toberemoved.encapsulates() && !parent.encapsulates()) {
            //if the parent doesn't encapsulate and toberemoved does then
            //we should do the opposite and merge tobereomved with parent
            Set<Node> children = parent.getNodes();
            tree.deleteChild(parent);
            //tree.deleteChild(toberemoved);
            //parent = toberemoved;
            for (Integer i : parent.getIDs()) {
                toberemoved.setID(i);
            }
            for (Node node : children) {
                parent.addNode(node);
            }
        } else {
            tree.deleteChild(toberemoved);
            for (Integer i : toberemoved.getIDs()) {
                parent.setID(i);
            }
            for (Node n : toberemoved.getNodes()) {
                parent.addNode(n);
            }
        }

        return tree;
    }

    public static void prettyPrintTree(IClusterLevel tree) {
        prettyPrintTree(tree, 0);
    }

    private static void prettyPrintTree(IClusterLevel tree, int tabIndex) {
        for (int i = 0; i < tabIndex; i++) {
            System.out.print("\t");
        }
        System.out.println("Cluster " + tree.getIDs() + "[");
        if (tree.encapsulates()) {

            for (IClusterLevel t : ((ClusterNode) tree).getChildren()) {
                prettyPrintTree(t, tabIndex + 1);
            }
        } else {
            for (int i = 0; i < tabIndex; i++) {
                System.out.print("\t");
            }
            for (Node n : tree.getNodes()) {
                System.out.print(" " + n);
            }
            System.out.println();

        }
        for (int i = 0; i < tabIndex; i++) {
            System.out.print("\t");
        }
        System.out.println("]");
    }

    public static List<Integer> getIDs(IClusterLevel tree) {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        getIDsInternal(tree,ret);
        
        return ret;
    }

    private static List<Integer> getIDsInternal(IClusterLevel tree, ArrayList<Integer> list){
        list.addAll(tree.getIDs());
        if (tree.encapsulates()) {
            Set<IClusterLevel> l = ((ClusterNode) tree).getChildren();
            for (IClusterLevel c : l) {
                getIDsInternal(c,list);
            }
        }
        return list;
    }

    public static void printIDs(IClusterLevel tree) {
        for (Integer i : tree.getIDs()) {
            System.out.print(i + ",");

        }
        System.out.println();
        if (tree.encapsulates()) {
            for (IClusterLevel c : ((ClusterNode) tree).getChildren()) {
                printIDs(c);
            }
        }
    }
    
    
    public static IClusterLevel getParentOfNodeInTree(Node node, ClusterHead tree){
        
        Stack<IClusterLevel> toVisit = new Stack<IClusterLevel>();
        
        toVisit.addAll(tree.getChildren());
        
        while(!toVisit.isEmpty()){
            IClusterLevel c = toVisit.pop();
            if(c.contains(node)){
                
                if(!c.encapsulates()){
                    //We've hit a ClusterLeaf so we've hit the bottom
                    //of the tree so it's time to stop
                    return c;
                }else{
                    //current level's children will have node, so
                    //everything else on the stack won't, so empty the
                    //stack.
                    toVisit.removeAllElements();
                    for(IClusterLevel child:((ClusterNode) c).getChildren())
                        toVisit.push(child);
                }
            }
        }
        
        return tree; //this will never execute but we need to shut javac up
        
    }

	/**
	 * Remove all empty nodes. This method will locate and remove all nodes in the
	 * tree that contain nothing. The children of this empty node will replace it.
	 * @param ch
	 * @return the modified tree (does in place so can be ignored).
	 */
	public static ClusterHead prune(ClusterHead ch){
		if(ch.getChildren().size() == 1){
			
			IClusterLevel child = null;
			for(IClusterLevel c: ch.getChildren()){
				child = c;
			}
			if(child.encapsulates()){
				ch.setChildren(((ClusterNode)child).getChildren());

			
				ch.deleteChild(child);
			
				return prune(ch);
			}
		}
		return ch;
	}
        
        public static boolean isCyclic(IClusterLevel c){
            
            Stack<IClusterLevel> toVisit = new Stack<IClusterLevel>();
            Set<IClusterLevel> seen = new HashSet<IClusterLevel>();
            
            toVisit.push(c);
            
            while(!toVisit.isEmpty()){
                IClusterLevel current = toVisit.pop();
                if(!current.encapsulates()) continue; //ignore leaves - they can't be cyclic.
                
                ClusterNode cast = (ClusterNode)current;
                
                if(seen.contains(current)) return true;
                
                seen.add(current);
                
                for(IClusterLevel cn: cast.getChildren()){
                    toVisit.push(cn);
                }
                
                
            }
            
            return false;
            
        }
}
